package 滑动窗口And双指针;

import org.junit.Test;

import java.util.TreeMap;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/2 14:36
 */
public class lc6911不间断得子数组 {

    /*
      首先要明白一些简单的数学逻辑

      长度为 n 的数组 有多少个子数组？
      个数 ： = n + n - 1 + n - 2 + 。。。。。1  = （n + 1） n / 2

       ==
       总是容易陷入另外的一种思维方式中去！
       比如： 什么时候  以 i 结尾， 这种思维方式比较的方便， 什么时候以
       i 开头的这种思维方式比较方便！
     */


    /*
     能过 ，但是这个 解法的时间复杂度， 不太好说， 主要取决于数据量
     优化的点就是： while 循环那里， 可以优化掉 内层的for 循环
     */
    public long solution(int nums[]){
        long ans = 0;
        int max ,min;
        max = min = nums[0];
        for(int l = 0, r = 0;r < nums.length;r++){
            max = Math.max(max,nums[r]);
            min = Math.min(min,nums[r]);
            while(max - min > 2){
                /*
                 这样写， 问题 就出来了， l 向右移动的过程中
                 怎么快速的求出  max 和 min  的最新的值？
                 如果直接遍历的话，那可 就有点粗糙了！
                 */
                l++;
                max = min = nums[l];

                for(int i = l;i <= r;i++){
                    max = Math.max(max,nums[i]);
                    min = Math.min(min,nums[i]);
                }
            }
            ans += r - l + 1;
        }
        return ans;
    }

    @Test
    public void test(){
        int nums[] = {5,4,2,4};
        System.out.println(solution(nums));
        System.out.println(solve(nums));
    }



    /*
     可以借鉴下 Arignote的写法
     */


    public long solve(int nums[]){
        long ans = 0;
        TreeMap<Integer,Integer> window = new TreeMap<>((a,b) -> a - b);
        for(int l = 0,r = 0;r < nums.length;r++){
            window.put(nums[r],window.getOrDefault(nums[r],0) + 1); //

            while(window.lastKey() - window.firstKey() > 2){
                Integer temp = window.get(nums[l]);
                if(temp == 1){
                    window.remove(nums[l]);
                }else{
                    window.put(nums[l],temp - 1);
                }
                l++;
            }
            ans += r - l + 1;
        }
        return ans;
    }




}
